package binary_tree_implementation

import "algo-sdk-go/algo/data_struct/tree"

type BinaryTree struct {
}

// 根据先序遍历和中序遍历 构造二叉树
func (bt *BinaryTree) Array2BTByPreOrder_InOrder(preOrder, inOrder []int) *tree.TreeNode {
	if len(preOrder) == 0 || len(inOrder) == 0 || len(inOrder) != len(preOrder) {
		return nil
	}
	divideValue := preOrder[0]
	leftInOrder, rightInOrder := divideInOrder(divideValue, inOrder)
	leftPreOrder, rightPreOrder := dividePreOrder(len(leftInOrder), preOrder)

	root := tree.NewTreeNodeWithValue(divideValue)
	root.Left = bt.Array2BTByPreOrder_InOrder(leftPreOrder, leftInOrder)
	root.Right = bt.Array2BTByPreOrder_InOrder(rightPreOrder, rightInOrder)
	return root
}

// 根据后序遍历和中序遍历 构造二叉树
func (bt *BinaryTree) Array2BTByPostOrder_InOrder(postOrder, inOrder []int) *tree.TreeNode {
	return nil
}

func dividePreOrder(length int, preOrder []int) ([]int, []int) {
	var (
		leftPreOrder, rightPreOrder []int
	)

	if len(preOrder) == 1 {
		leftPreOrder = []int{}
		rightPreOrder = []int{}
	} else {
		leftPreOrder = preOrder[1 : length+1]
		rightPreOrder = preOrder[length+1:]
	}
	return leftPreOrder, rightPreOrder
}
func divideInOrder(index int, inOrder []int) ([]int, []int) {
	var right []int

	for i, i2 := range inOrder {
		if index == i2 {
			left := inOrder[:i]
			if i+1 <= len(inOrder) {
				right = inOrder[i+1:]
			}
			return left, right
		}
	}
	return nil, nil
}
